package com.gofaraway.service.student.leetCodeV2.双指针;

/**
 * @author ChenPeng
 * @date 2025/7/6 17:40
 */
public class 接雨水 {

    /**
     * 辅助数组解法 双指针解法需要根据 根据这个版本的解法，延展
     *
     * @param height
     * @return
     */
    public int trap(int[] height) {

        int n = height.length;
        //初始化一个数组 每个位置i代表 ： 0-i范围的最大值
        int[] L_Max = new int[n];
        //0-0位置的最大值就是0位置的数，先初始化
        L_Max[0] = height[0];
        for (int i = 1; i < n; i++) {
            int max = Math.max(L_Max[i - 1], height[i]);
            L_Max[i] = max;
        }

        //初始化一个数组 每个位置i代表 ： i~n-1 范围的最大值
        int[] R_Max = new int[n];
        R_Max[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            int max = Math.max(height[i], R_Max[i + 1]);
            R_Max[i] = max;
        }

        //结算
        int ans = 0;
        for (int i = 1; i < n - 1; i++) {
            int lMax = L_Max[i];
            int rMax = R_Max[i];
            int min = Math.min(lMax, rMax);
            //每个位置能蓄的水
            int value = Math.max(min - height[i], 0);
            ans += value;
        }
        return ans;
    }


}
